package com.leetcode.程序员面试金典.hard;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-01-27 16:01
 */
public class 面试题_16_03_交点 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] start1 = {0, 0};
    int[] end1 = {0, 1};
    int[] start2 = {1, 0};
    int[] end2 = {1, 1};
    double[] intersection = solution.intersection(start1, end1, start2, end2);
    System.out.println(Arrays.toString(intersection));
  }

  static
  class Solution {
    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {

      int x1 = start1[0];
      int y1 = start1[1];
      int x2 = end1[0];
      int y2 = end1[1];

      int x3 = start2[0];
      int y3 = start2[1];
      int x4 = end2[0];
      int y4 = end2[1];

      double[] result = new double[]{Integer.MAX_VALUE, Integer.MAX_VALUE};

      // 线段只有一个点 ???

      // 平行
      if ((y2 - y1) * (x4 - x3) == (y4 - y3) * (x2 - x1)) {
        if((y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1)) {
          // 共线
          /*
            (x1, y1) 是否在线段 (x3, y3) ~ (x4, y4) 上
            (x2, y2) 是否在线段 (x3, y3) ~ (x4, y4) 上
            (x3, y3) 是否在线段 (x1, y1) ~ (x2, y2) 上
            (x4, y4) 是否在线段 (x1, y1) ~ (x2, y2) 上
          */
          if (isCommonLine(x1, y1, x3, y3, x4, y4)) {
            updateResult(x1, y1, result);
          }
          if (isCommonLine(x2, y2, x3, y3, x4, y4)) {
            updateResult(x2, y2, result);
          }
          if (isCommonLine(x3, y3, x1, y1, x2, y2)) {
            updateResult(x3, y3, result);
          }
          if (isCommonLine(x4, y4, x1, y1, x2, y2)) {
            updateResult(x4, y4, result);
          }
        }
      } else {
        double t1 = (1.0 * (y1 - y3) * (x4 - x3) - (x1 - x3) * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3));
        double t2 = (1.0 * (y3 - y1) * (x2 - x1) - (x3 - x1) * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (y4 - y3) * (x2 - x1));
        if (t1 >= 0 && t1 <= 1 && t2 >= 0 && t2 <= 1) {
          result = new double[] {x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)};
        }
      }
      return result[0] == Integer.MAX_VALUE ? new double[]{} : result;
    }

    private boolean isCommonLine(int x, int y, int x1, int y1, int x2, int y2) {
      double t;
      if (x1 == x2) {
        t = (y - y1) * 1.0 / (y2 - y1);
      } else {
        t = (x - x1) * 1.0 / (x2 - x1);
      }
      return t >= 0 && t <= 1;
    }

    private void updateResult(double x, double y, double[] result) {
      if (x < result[0] || (result[0] == x && y < result[1])) {
        result[0] = x;
        result[1] = y;
      }
    }
  }

}
